#include <iostream>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <algorithm>
#include <ctime>
#include <iterator>
using namespace std;

typedef vector<int> IntVec;

int chop(int value, const IntVec& integers) {
	if (integers.size() > 0 && integers.front() <= value && value <= integers.back()) {
		int begin = 0;
		int end = integers.size();
		while (begin < end) {
			int maxInRange = integers[end < integers.size() ? end : integers.size()-1];
			int middle = static_cast<int>( static_cast<double>(value) / static_cast<double>(maxInRange) * static_cast<double>(end - begin) );
			middle = middle < integers.size() ? middle : integers.size() - 1;
			if (value == integers[middle]) {
				return middle;
			} else if (value > integers[middle]) {
				begin = middle + 1;
			} else if (value < integers[middle]) {
				end = middle - 1;
			}
		}
	}
	return -1;
}

int main(int argc, char* argv[]) {
	IntVec vec0;
	assert(-1 == chop(3, vec0));

	int array1[] = { 1 };
	IntVec vec1(array1, array1 + sizeof(array1) / sizeof(array1[0]));
	assert(-1 == chop(3, vec1));
	assert(0 == chop(1, vec1));

	int array2[] = { 1, 3, 5 };
	IntVec vec2(array2, array2 + sizeof(array2) / sizeof(array2[0]));
	assert(0 == chop(1, vec2));
	assert(1 == chop(3, vec2));
	assert(2 == chop(5, vec2));
	assert(-1 == chop(0, vec2));
	assert(-1 == chop(2, vec2));
	assert(-1 == chop(4, vec2));
	assert(-1 == chop(6, vec2));

	int array3[] = { 1, 3, 5, 7 };
	IntVec vec3(array3, array3 + sizeof(array3) / sizeof(array3[0]));
	assert(0 == chop(1, vec3));
	assert(1 == chop(3, vec3));
	assert(2 == chop(5, vec3));
	assert(3 == chop(7, vec3));
	assert(-1 == chop(0, vec3));
	assert(-1 == chop(2, vec3));
	assert(-1 == chop(4, vec3));
	assert(-1 == chop(6, vec3));
	assert(-1 == chop(8, vec3));

	int array4[] = { 0, 1, 1, 3, 4, 5, 5, 5, 8, 8 };
	IntVec vec44(array4, array4 + sizeof(array4) / sizeof(array4[0]));
	assert(4 == chop(4, vec44));

	if (argc > 1) {
		int n = atoi(argv[1]);
		int m = atoi(argv[2]);
		IntVec vec4(n, 0);
		srand(time(0));
		for (int i = 0; i < n; i++) {
			vec4[i] = rand() % m;
		}
		sort(vec4.begin(), vec4.end());
		int randVal = vec4[rand() % n];
		copy(vec4.begin(), vec4.end(), ostream_iterator<int>(cout, " "));
		cout << "\n" << randVal << endl;
		assert(randVal == chop(randVal, vec4));
	}
}
